package LeetCodeHot100;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合总和
 *给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 *
 * 思路：排列组合的思路
 *      可以使用回溯的思想去解决问题
        递归头：
 */
public class LeetCode39 {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,0,target);
        return res;
    }

    /**
     * 回溯方法
     * @param c
     * @param index
     * @param target
     */
    private void dfs(int[] c,int index,int target){
        if(target<0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = index; i <c.length ; i++) {
            if(c[i] <= target){
                tmp.add(c[i]);
                dfs(c,i,target-c[i]);   // 需要注意题意，同一个数字可以无限地重复取值，所以要这么干
                tmp.remove(tmp.size()-1);
            }
        }
    }
}
